package com.leetcode.algorithm.y22.m07.w4;

import java.util.ArrayDeque;
import java.util.Deque;

/**
 * 503. 下一个更大元素 II
 * 
 * https://leetcode.cn/problems/next-greater-element-ii/
 * 
 * @author jie.deng
 *
 */
class Question0503Solution01 {

	public int[] nextGreaterElements(int[] nums) {
		int len = nums.length;
		int[] arr = new int[len];
		Deque<Integer> stack = new ArrayDeque<>();
		int greaterNum = 0;
		for (int i = len - 1; i >= 0; i--) {
			greaterNum = add2AscStack(nums[i], stack);
			arr[i] = greaterNum;
		}
		for (int i = len - 1; i >= 0; i--) {
			greaterNum = add2AscStack(nums[i], stack);
			arr[i] = greaterNum;
		}
		return arr;
	}

	private int add2AscStack(int num, Deque<Integer> stack) {
		while (!stack.isEmpty() && stack.peek().intValue() <= num) {
			stack.pop();
		}
		int greaterNum = -1;
		if (!stack.isEmpty()) {
			greaterNum = stack.peek();
		}
		stack.push(num);
		return greaterNum;
	}

}